package com.desheng.bigdata.ds.queue;

/**
 * 最大优先级队列
 *  队列的特点，就是先进先出，所谓FIFO，但是一旦有了优先级，就不一定是FIFO了，而是优先级最高的先出
 *  所以我们怎么去理解这个最高优先级呢，一个比较灵活的方式就是通过堆来进行处理，为什么呢？因为堆的结构
 *  最底层的节点，就是最大的一个节点，那么自然可以理解为优先级最高的，那么出队就可以理解为删除堆的根节点了，
 *  入队就可以理解为往堆中插入一个节点了。
 *  这样就可以简化处理流程
 */
public class MaxPriorityQueue<T extends Comparable<T>> {
    //队列的长度
    private int size;
    private T[] items;//存放队列元素的数组

    private static final int DEFAULT_CAPACITY = 10;
    public MaxPriorityQueue(int capacity) {
        this.items = (T[])new Comparable[capacity + 1];//第一个节点不存储元素
    }

    public MaxPriorityQueue() {
        this.items = (T[])new Comparable[DEFAULT_CAPACITY + 1];//第一个节点不存储元素
    }

    /*
        元素入队其实，就是把该元素放入到堆中合适的位置
     */
    public void enqueue(T data) {
        if(size == items.length - 1) {//说明上一次已经添加到数组的最后一个元素了，数组需要进行扩容
            T[] newObjs = (T[])new Comparable[items.length + items.length / 2];
            System.arraycopy(items, 1, newObjs, 1, size);
            items = newObjs;
        }
        //注意，因为在索引0的位置上不放元素，所以需要先+
        items[++size] = data;
        //需要做的一件事，是将该元素调整到堆中指定的恰当位置
        rise(size);
    }

    /*
        上浮index索引位置处的元素到执行的位置
        该元素如何和自己的父节点比较，比父节点大，二者就要交换位置
     */
    private void rise(int index) {
        while (index > 1) {
            if(!less(index / 2, index)) {
                break;
            }
            //二者就要交换位置
            exchange(index / 2, index);
            index = index / 2;
        }
    }

    //从队列中移除优先级最高的元素
    public T dequeue(){
        T max = items[1];
        //交换第一个元素和最后一个元素
        exchange(1, size);
        size--;
        //再一次调整堆有序
        sink(1);
        return max;
    }

    /*
        将index位置处的元素开始调整，使之成为一个堆
     */
    private void sink(int index) {
        while (2 * index <= size) {//其左子节点是存在的
            int max = 2 * index;
            //找到子节点中较大的子节点
            if((max + 1) <= size) {// 有右子节点
                if(less(2 * index, max + 1)) {
                    max = max + 1;
                }
            }
            //确定了较大的子节点之后，就和自己进行比较，是否需要交换元素
            if(less(max, index)) {
                break;
            }
            exchange(index, max);
            index = max;
        }
    }


    private void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }



}
